/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#ifndef ALGOGRAPH_BN0149RN

#define ALGOGRAPH_BN0149RN


#include <iostream>
#include <set>
#include <vector>
#include <map>


namespace AlgoGraph
{

    namespace // anonymous
    {

        /**
         * @brief
         *
         * @param graph graph
         * @param node current node
         * @param L visited node
         * @param S no visited node
         * @param result should not be allocated. output : result[position] = element
         *
         * @return acyclic ? true : false;
         */
        template <class U, class G>
            bool topologicalVisit( G &graph, const U node, std::set<U> &L, std::set<U> &S, std::vector<U> &result ) // TEST : OK
            {
                if( L.count( node ) > 0 )
                    return true;

                if( S.count( node ) == 0 )
                    return false;

                S.erase( node );

                bool acyclic = true;

                for (typename std::set<U>::iterator it = graph[node].begin(); it != graph[node].end(); ++it)
                    if( !topologicalVisit( graph, *it, L, S, result ) )
                        acyclic = false;

                result.push_back(node);
                L.insert(node);
                return acyclic;
            }

        /**
         * @brief
         *
         * @param graph graph
         * @param node current node
         * @param L visited node
         * @param S no visited node
         *
         * @return acyclic ? true : false;
         */
        template <class U, class G>
            bool existesPath( G &graph, const U node, const U search, std::set<U> &L, std::set<U> &S ) // TEST : OK
            {
                if( L.count( node ) > 0 )
                    return false;

                if( S.count( node ) == 0 )
                    return false;

                S.erase( node );

                if( node == search )
                    return true;

                for (typename std::set<U>::iterator it = graph[node].begin(); it != graph[node].end(); ++it)
                    if(existesPath( graph, *it, search, L, S ))
                        return true;

                L.insert(node);
                return false;
            }

    }

    /**
     * @brief reverses a graph
     *
     * @param G-the graph to reverse
     * @param result-the reversed graph
     */
    void reverseGraph( std::vector<std::set<unsigned int> > &G, std::vector<std::set<unsigned int> > &result );


    /**
     * @brief
     *
     * @param graph graphe
     * @param S All node (No visited node)
     * @param result ne doit pas étre aloué. output : result[position] = element
     *
     * @return acyclic ?
     */
    template <class U, class G>
        bool topologicalSorting( G &graph, std::set<U> S, std::vector<U> &result ) // TEST : OK
        {
            bool acyclic = true;

            // sorted
            std::set<U> L;

            while( S.size() > 0 )
                if( topologicalVisit<U, G>( graph, *(S.begin()), L, S, result ) == false )
                    acyclic = false;

            return acyclic;
        }

    /**
     * @brief
     *
     * @param graph
     * @param S All node (No visited node)
     * @param noGraph
     * @param result doit etre aloué. result[ element ] = id de la partition
     */
    template <class U, class G, class R>
        unsigned int stronglyConnected( G &graph, std::set<U> S, G &noGraph, R &result ) // TEST : OK
        {
            unsigned int id = 0;
            std::vector<U> r1;
            std::vector<U> r2;

            // sorted
            std::set<U> L;

            topologicalSorting( graph, S, r1 );

            for (int i = r1.size()-1; i >= 0; i--)
            {
                r2.clear();
                topologicalVisit( noGraph, r1[i], L, S, r2 );

                for (unsigned int j = 0; j < r2.size(); j++)
                    result[r2[j]] = id;

                if(r2.size() > 0)
                    ++id;
            }

            return id;
        }

    template <class U, class G>
        unsigned int stronglyConnected( G &graph, std::set<U> S, std::vector<U> &res, std::vector<std::set<U> > &result ) // TEST : OK
        {
            std::vector<std::set<unsigned int> > reverseG;
            reverseGraph(graph, reverseG);

            res.resize(S.size());
            result.resize(stronglyConnected(graph, S, reverseG, res));
            for ( unsigned int i = 0; i < res.size(); ++i )
                result[res[i]].insert(i);
            return result.size();
        }

    /**
     * @brief
     *
     * @param graph
     * @param S All node (No visited node)
     * @param result doit étre aloué. result[ element ] = id de la partition
     */
    template <class U, class G, class R>
        void connected( G &graph, std::set<U> S, R &result )
        {
            unsigned id=0;
            std::vector<U> r;

            // sorted
            std::set<U> L;

            while( S.size() > 0 )
            {
                r.clear();
                topologicalVisit( graph, *(S.begin()), L, S, r );
                for (unsigned int i = 0; i < r.size(); i++)
                    result[ r[i] ] = id;

                if(r.size() > 0)
                    ++id;
            }

        }

    /**
     * @brief this function is testing if a graph is biparti,
     * and also fills graph with the cells contained in each cluster,
     * and fills cells with the corresponding cluster for each cell
     * @param graph - is the graphe we work on
     * @param clusters - the clusters with the cells they contain
     * @param cells - for each cell the cluster
     * @return true if graph is biparti, false otherwise
     */
    bool bipartiGraphClusters( std::vector<std::set<unsigned int> > &graph,
            std::vector<std::set<unsigned int> > &clusters, std::vector<unsigned int> &cells);

    bool bipartiGraphCluster( std::vector<std::set<unsigned int> > &graph,
            std::vector<std::set<unsigned int> > &clusters,
            std::vector<unsigned int> &cells,
            unsigned int begin, std::vector<int> &visited );


    /**
     * @brief search if exists a path with a -> b
     *
     * @param G graphe
     * @param a begin
     * @param b end
     *
     * @return exists Path ? true : false;
     */
    template <class T>
        bool existsPath( std::vector<std::set<T> > &G, T a, T b) // TEST : OK
        {
            std::set<T> L;
            std::set<T> S;
            std::vector<T> result;
            for (T i = 0; i < G.size(); i++)
                S.insert(i);

            return existesPath( G, a, b, L, S);
        }

    /**
     * @brief search if exists a path with a -> b
     *
     * @param G graphe
     * @param a begin
     * @param b end
     * @param N no use this node for the path
     *
     * @return exists Path ? true : false;
     */
    template <class T>
        bool existsPath( std::vector<std::set<T> > &G, T a, T b, std::set<T> N)
        {
            std::set<T> L;
            std::set<T> S;
            std::vector<T> result;
            for (T i = 0; i < G.size(); i++)
                S.insert(i);
            for (typename std::set<T>::iterator it = N.begin(); it != N.end(); ++it)
            {
                S.erase( *it );
                L.insert( *it );
            }

            return existesPath( G, a, b, L, S);
        }


}



#endif /* end of include guard: ALGOGRAPH_BN0149RN */
